package com.yulongtian.weekCompetition.month202211.week2;

import java.sql.SQLOutput;
import java.util.*;

/**
 * 6235. 逐层排序二叉树所需的最少操作数目
 *
 * @author yulongTian
 * @create 2022-11-13 10:40
 */
public class Test03 {
    public static void main(String[] args) {

    }

    /**
     * 层序遍历+置换环
     *
     * @param root
     * @return
     */
    public int minimumOperations(TreeNode root) {
        List<int[]> temp = new ArrayList<>();
        //将每层的节点存入数组中
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);
        //层序遍历  将每一层放入数组中
        while (!queue.isEmpty()) {
            int tempSize = queue.size();
            int[] tempArr = new int[tempSize];
            for (int i = 0; i < tempSize; i++) {
                TreeNode poll = queue.poll();

                tempArr[i] = poll.val;
                if (poll.left != null) {
                    queue.add(poll.left);
                }
                if (poll.right != null) {
                    queue.add(poll.right);
                }
            }
            //保存数组
            temp.add(tempArr);
        }
        int res=0;
        for (int[] arr : temp) {
            //排序后的数组 用于对照
            int[] clone = arr.clone();
            Arrays.sort(clone);
            Map<Integer,Integer> map=new HashMap<>();
            //保存  值和索引，便于通过值来求得索引
            for (int i = 0; i < clone.length; i++) {
                map.put(clone[i],i);
            }
            for (int i = 0; i < arr.length; i++) {
                //ai!=bi  一直交换
                while (arr[i]!=clone[i]){
                    swap(arr,i,map.get(arr[i]));
                    res++;
                }
            }
        }
        return res;
    }

    /**
     * 交换i和j下标位置的元素
     *
     * @param arr
     * @param i
     * @param j
     */
    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
